package day_7_11;

import java.util.LinkedList;
import java.util.Queue;

public class Main1 {
    /**
     * 994. 腐烂的橘子
     * https://leetcode.cn/problems/rotting-oranges/description/?envType=study-plan-v2&envId=top-100-liked
     */
    // BFS
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};

    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        Queue<int[]> q = new LinkedList<>(); // 用来层序遍历，进行橘子的腐烂的
        int flash = 0;// 用来表示存在多少个新鲜橘子
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(grid[i][j] == 1) {
                    flash++;
                }else if(grid[i][j] == 2) {
                    q.offer(new int[]{i,j});
                }
            }
        }

        int ret = 0;
        // 进行判断flash > 0  这个条件是为了当可以全部腐烂的时候，队列中还存在最后一次遍历，但是都进行腐烂了，所以不需要对其进行遍历
        // 这样可以防止多余的遍历
        while(flash > 0 && !q.isEmpty()) {
            ret++;
            int size = q.size();
            while(size-- != 0) {
                int[] t = q.poll();
                int a = t[0];
                int b = t[1];
                for(int k = 0;k < 4;k++) {
                    int x = a + dx[k];
                    int y = b + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        flash--;
                        grid[x][y] = 2;
                        q.offer(new int[]{x,y});
                    }
                }
            }
        }

        return flash > 0 ? -1 : ret;
    }
}
